#include <cmath>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
  // 记录每个节点的入度信息
  vector<int> in_degree(numCourses, 0);
  // 记录每个节点的后继节点
  unordered_map<int, vector<int>> preCourse;
  for (int i = 0; i < prerequisites.size(); ++i) {
    preCourse[prerequisites[i][1]].push_back(prerequisites[i][0]);
    // 记录入度信息
    in_degree[prerequisites[i][0]]++;
  }
  queue<int> q;
  int count = 0;
  for (int i = 0; i < numCourses; ++i) {
    if (in_degree[i] == 0) {
      // 将入度为0的节点加入处理队列中
      q.push(i);
      // 记录已处理节点数量
      ++count;
    }
  }
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    // 把与当前节点相邻的节点的入度减一
    if (preCourse.find(cur) != preCourse.end()) {
      for (int i = 0; i < preCourse[cur].size(); i++) {
        --in_degree[preCourse[cur][i]];
        if (in_degree[preCourse[cur][i]] == 0) {
          q.push(preCourse[cur][i]);
          ++count;
        }
      }
    }
  }
  if (count == numCourses)
    return true;
  return false;
}

// 性能优化
bool canFinish1(int numCourses, vector<vector<int>> &prerequisites) {
  // 记录每个节点的入度信息
  vector<int> in_degree(numCourses, 0);
  // 记录每个节点的后继节点
  vector<vector<int>> preRequestCourse(numCourses);
  for (auto &p : prerequisites) {
    preRequestCourse[p[1]].push_back(p[0]);
    in_degree[p[0]]++;
  }
  // 使用数组+双指针模拟队列
  vector<int> q{numCourses};
  int head = 0;
  int tail = 0;
  int count = 0;
  for (int i = 0; i < numCourses; ++i) {
    if (in_degree[i] == 0) {
      // 将入度为0的节点加入处理队列中
      q[tail++] = i;
      // 记录已处理节点数量
      ++count;
    }
  }
  while (head < tail) {
    int cur = q[head++];
    // 把与当前节点相邻的节点的入度减一
    for (auto &k : preRequestCourse[cur]) {
      if (--in_degree[k] == 0) {
        q[tail++] = k;
      }
    }
  }
  if (count == numCourses)
    return true;
  return false;
}